using System;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0336. 回文对")]
    public class No0336_PalindromePairs : AbsBaseTestItem
    {
        /*
        给定一组唯一的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
        */

        public override void OnTest()
        {
            Assert.TestExe(PalindromePairs,
                new string[] { "abcd", "dcba", "lls", "s", "sssll" },
                new List<IList<int>>()
                {
                    new int[] {0, 1},
                    new int[] {1, 0},
                    new int[] {3, 2},
                    new int[] {2, 4},
                });
            Assert.TestExe(PalindromePairs,
                new string[] { "bat", "tab", "cat" },
                new List<IList<int>>()
                {
                    new int[] {0, 1},
                    new int[] {1, 0},
                });
        }

        class Node
        {
            public int[] ch = new int[26];
            public int flag;

            public Node()
            {
                flag = -1;
            }
        }
        public IList<IList<int>> PalindromePairs(string[] words)
        {
            List<Node> tree = new List<Node>();
            void insert(string s, int id)
            {
                int len = s.Length, add = 0;
                for (int i = 0; i < len; i++)
                {
                    int x = s[i] - 'a';
                    if (tree[add].ch[x] == 0)
                    {
                        tree.Add(new Node());
                        tree[add].ch[x] = tree.Count - 1;
                    }
                    add = tree[add].ch[x];
                }
                tree[add].flag = id;
            }
            bool isPalindrome(string s, int left, int right)
            {
                int len = right - left + 1;
                for (int i = 0; i < len / 2; i++)
                {
                    if (s[left + i] != s[right - i])
                    {
                        return false;
                    }
                }
                return true;
            }

            int findWord(string s, int left, int right)
            {
                int add = 0;
                for (int i = right; i >= left; i--)
                {
                    int x = s[i] - 'a';
                    if (tree[add].ch[x] == 0)
                    {
                        return -1;
                    }
                    add = tree[add].ch[x];
                }
                return tree[add].flag;
            }

            tree.Add(new Node());
            int n = words.Length;
            for (int i = 0; i < n; i++)
            {
                insert(words[i], i);
            }
            List<IList<int>> ret = new List<IList<int>>();
            for (int i = 0; i < n; i++)
            {
                int m = words[i].Length;
                for (int j = 0; j <= m; j++)
                {
                    if (isPalindrome(words[i], j, m - 1))
                    {
                        int leftId = findWord(words[i], 0, j - 1);
                        if (leftId != -1 && leftId != i)
                        {
                            ret.Add(new int[] { i, leftId });
                        }
                    }
                    if (j != 0 && isPalindrome(words[i], 0, j - 1))
                    {
                        int rightId = findWord(words[i], j, m - 1);
                        if (rightId != -1 && rightId != i)
                        {
                            ret.Add(new int[] { rightId, i });
                        }
                    }
                }
            }
            return ret;
        }
    }
}
